#include "heap.h"

//huffman树的结点
template<class T>
struct HuffmanNode
{
    HuffmanNode(T weight)
        :_weight(weight)
    {
        _left=NULL;
        _right=NULL;
        _parent=NULL;
    }

    T _weight;
    HuffmanNode<T>* _left;
    HuffmanNode<T>* _right;
    HuffmanNode<T>* _parent;

};

//typedef HuffmanNode<T> Node;
//template<class T>
//struct CompareWeight
//{
//  bool operator()(const HuffmanNode<T>* left,const HuffmanNode<T>* right)
//  {
//    return left->_weight<right->_weight;
//  }
//};
template<class T>
class Huffman 
{
    typedef HuffmanNode<T> Node;

    template<class T1>
        struct CompareWeight
        {
            bool operator()(const Node* left,const Node* right)
            {
                return left->_weight<right->_weight;
            }
        };
public:
    Huffman()
        :_root(NULL)
    {}

    ~Huffman()
    {}

    //----------------------获取huffman树的根节点----------------
    HuffmanNode<T>* GetRoot()
    {
        return _root;
    }

    //----------------------构造huffman树------------------------
    Node* MakeHuffman(T* arr,size_t size,const T& invalid)
    {
        //1.使用数组中的有效元素建最小堆
        Heap<Node*,CompareWeight<T> > min_heap;
        for(int i=0;i<size;i++)
        {
            if(arr[i]!=invalid)
            {
                Node* node=new Node(arr[i]);
                min_heap.Push(node);
            }
        }

        //2.依次取堆顶两次求出最小的两个值
        while(min_heap.Size()>1)
        {
            Node* left=min_heap.Top();
            min_heap.Pop();
            Node* right=min_heap.Top();
            min_heap.Pop();
            Node* parent=new Node(left->_weight+right->_weight);
            //链接结点
            parent->_left=left;
            parent->_right=right;
            left->_parent=parent;
            right->_parent=parent;
            //把他们之和放入堆中进行调整
            min_heap.Push(parent);
        }
        //此时最后一个堆顶就是哈夫曼树的根顶
        _root=min_heap.Top();
        return _root;
    }
    //------------------打印huffman树------------------
    void PrintHuffman()
    {
        Node* root=_root;
        _PrintHuffman(root);
    }
protected:
    void _PrintHuffman(Node* root)
    {
        if(root==NULL)
            return;
        cout<<root->_weight<<" ";
        _PrintHuffman(root->_left);
        _PrintHuffman(root->_right);
    }
private:
    Node* _root;
};

///////////////////////////////////////////////////////
// 测试huffman树
///////////////////////////////////////////////////////

void TestHuffman()
{
    int arr[]={0,0,1,3,5,7,0,0};
    Huffman<int> hm;
    hm.MakeHuffman(arr,sizeof(arr)/sizeof(arr[0]),0);
    hm.PrintHuffman();
}
